package com.ming.learn.from.carl.linkedlist;

import com.ming.commons.utils.ListNode;

/*
第206题：反转链表
 */
public class Of20201222LeetCode206 {
    /*
    题意：反转一个单链表。
    示例: 输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL
     */
    /*
    双指针法
    时间复杂度 O(n)
    空间复杂度 O(1)
     */
    static ListNode reverseList1(ListNode head){
        ListNode newHead=null; // 新链表的头
        ListNode cur = head;   // 要转移节点的指针
        while (head!=null){
            head=head.next;
            cur.next=newHead;
            newHead = cur;
            cur=head;
        }
        return newHead;
    }

    /*
    递归法
     */
    static ListNode reverse(ListNode pre,ListNode cur){
        if(cur == null) return pre;
        ListNode temp = cur.next;
        cur.next = pre;
        // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    static ListNode reverseList2(ListNode head){
        return reverse(null, head);
    }

    public static void main(String[] args) {
        ListNode listNode = reverseList1(new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4)))));
        while (listNode!=null){
            System.out.print(listNode.val+"\t");
            listNode=listNode.next;
        }
    }
}
